"""
算法思想：采用分治法，将数组递归分为两个子数组，分别排序后再将两个有序子数组合并为一个有序数组。


代码解释：
分治过程：merge_sort函数递归将数组分为左右两个子数组，直至子数组长度为 1（天然有序）。
合并过程：merge函数将两个有序子数组合并为一个有序数组：
    用两个指针i和j分别遍历left和right数组。
    比较指针指向的元素，将较小的元素加入结果列表，并移动对应指针。
    遍历结束后，将剩余元素直接加入结果列表（因子数组已有序）。
时间复杂度：划分过程为O(logn)，合并过程为O(n)，整体时间复杂度为O(nlogn)，空间复杂度为O(n)（需额外存储合并结果）。
"""


def merge_sort(arr):
    # 递归终止条件：数组长度小于等于1时无需排序
    if len(arr) <= 1:
        return arr

    # 划分中点
    mid = len(arr) // 2

    # 递归排序左半部分
    left = merge_sort(arr[:mid])
    # 递归排序右半部分
    right = merge_sort(arr[mid:])

    # 合并两个有序子数组
    return merge(left, right)


def merge(left, right):
    """合并两个有序数组为一个有序数组"""
    result = []  # 存储合并结果
    i = j = 0  # i和j分别为left和right的指针

    # 比较两个子数组的元素，按序加入结果
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 将剩余元素加入结果（left或right可能有剩余）
    result.extend(left[i:])
    result.extend(right[j:])

    return result


# 测试
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print("归并排序结果:", sorted_arr)  # 输出: [5, 6, 7, 11, 12, 13]
